COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	EXTERNAL INTEGER ARRAY PRIMES[1:2] ∂ Bounds are ignored
C00003 00003	INTERNAL INTEGER PROCEDURE nearest_prime(
C00006 ENDMK
C⊗;
EXTERNAL INTEGER ARRAY PRIMES[1:2]; ∂ Bounds are ignored;
EXTERNAL INTEGER #PRIMES;
REQUIRE "PRIMES" LOAD_MODULE;

INTERNAL INTEGER PROCEDURE nearest_prime(
      REFERENCE INTEGER n);
∂ Takes as argument an integer n in the range covered by the EXTERNAL PRIMES
table and returns as a result the index in the PRIMES table of the nearest
prime to that n.  The REFERENCE argument n is set to that table entry.
;
   BEGIN "nearest_prime"
   INTEGER top, bot;
   IF
      ¬((0 < n)  ∧  (n ≤ PRIMES[#PRIMES]))
    THEN BEGIN
      PRINT(↓,"nearest_prime: 2 ≤ n ≤ ",PRIMES[#PRIMES],↓);
      RETURN(PRIMES[#PRIMES]);
      END;
   top ← LOCATION(PRIMES[#PRIMES]);
   bot ← LOCATION(PRIMES[1]);

      START_CODE "binary search"
      LABEL Test; ∂ Faster than linear search if #PRIMES>30;
      DEFINE Key=0, i=1, hi=2, lo=3;
      MOVE    hi,top;
      MOVE    lo,bot;
      MOVE    Key,n;

   Test:
      MOVEI   i,(lo); ∂ Find center of sub-table;
      ADDI    i,(hi);
      LSH     i,-1;
      CAMLE   Key,(i); ∂ Which half of sub-table is Key in?;
      AOSA    lo,i; ∂ Add 1 to compensate for truncation in LSH;
      MOVEI   hi,(i); ∂ New sub-table is half containing Key;
      CAIGE   lo,(hi); ∂ If sub-table contains only 1 element, we're done;
      JRST    Test;

      SUB     hi,bot;
      AOS     hi;
      MOVEM   hi,top;
      END        "binary search";

   IF
      (top > 1)
           ∧
      (PRIMES[top-1]+PRIMES[top]) LSH -1 ≥ n
    THEN
      top ← top-1;
   n ← PRIMES[top];
   RETURN(top);
   END   "nearest_prime";